package com.zm.demo.core.sort;

import java.util.Arrays;
import java.util.Random;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/3/10 13:17
 */
public class QuickSort {

    private static Random random = new Random();

    public static void main(String[] args){
        int[] s = new int[new Random().nextInt(500)];
        for (int i = 0; i < s.length; i++) {
            s[i] = new Random().nextInt(1000);
        }


        out.println(Arrays.toString(s));
        out.println(s.length);
        quickSort(s, 0, s.length-1);
        out.println(Arrays.toString(s));
        out.println(s.length);

    }

    public static void quickSort(int[] source, int start, int end) {
        int i = start;
        int j = end;
        int base = source[start];

        //i<j表示还没有遍历完整个数组列表，需要继续计算
        while (i<j){
            //如果i节点的值小于基准值，且i<j，则不需要处理，小的索引+1
            while (source[i]<base && i<j){
                i++;
            }
            //如果j节点的值大于基准值，且i<j，则不需要处理，大的索引-1
            while (source[j]>base && i<j){
                j--;
            }

            //走到这一步表示source[i]>=base并且souce[j]<=base
            //如果这两个值相等，即都等于base，则不需要计算，选其中一个索引递增或者递减即可
            //如果这两个值不相等，则表示source[i]>souce[j],两个值需要交换
            //继续下一轮循环
            if (source[i] == source[j] && i<j){
                j--;
            }else {
                int temp = source[i];
                source[i] = source[j];
                source[j] = temp;
            }
        }

        //如果i - 1 > start，表示有小于基准值的数据，递归处理；否则不作处理
        if (i-1 > start){
            quickSort(source, start, i-1);
        }

        //如果 j + 1 < end，表示有大于基准值的数据，递归处理，否则不作处理
        if (j+1<end){
            quickSort(source, j+1, end);
        }
    }
}
